// 邻接表
#pragma once

// 邻接表存储结构
template <typename V, typename E, int M = 10>
struct ALGraph
{
    // 弧结点
    struct ArcNode
    {
        E weight;
        int adjvex;
        ArcNode *nextarc;
    };

    // 顶点结点
    struct VexNode
    {
        V data;
        ArcNode *firstarc;
    };

    // 图结构
    VexNode vexs[M];
    int vexnum, arcnum;
    bool visited[M]; // 顶点的访问标志
};

// 初始化图 InitGraph(&G)
template <typename V, typename E, int M>
void InitGraph(ALGraph<V, E, M> &G)
{
    G.vexnum = G.arcnum = 0;
}

// 销毁图结构 DestroyGraph(&G)
template <typename V, typename E, int M>
void DestroyGraph(ALGraph<V, E, M> &G)
{
    // 释放每个顶点项链的弧结点
    for (int i = 0; i < G.vexnum; i++)
    {
        // 释放顶点 i 相连的弧结点
        auto &h = G.vexs[i].firstarc;
        while (h)
        {
            auto p = h;
            h = p->nextarc;
            delete p;
        }
    }

    // 将顶点数和弧数清零
    G.vexnum = G.arcnum = 0;
}

// 添加顶点 AddVertex(&G,vex)
// 向图 G 中添加顶点 vex，返回顶点的编号
template <typename V, typename E, int M>
int AddVertex(ALGraph<V, E, M> &G, V vex)
{
    if (G.vexnum == M)
        throw "Too many vertexes";
    int v = G.vexnum;
    G.vexs[v].data = vex;
    G.vexs[v].firstarc = nullptr;
    G.vexnum++;

    return v;
}

// 添加边 AddArc(&G,s,t,e)
// 向图 G 中添加 s 到 t 的弧，弧的权值为 e
template <typename V, typename E, int M>
void AddArc(ALGraph<V, E, M> &G, int s, int t, E e)
{
    if (s < 0 || s >= G.vexnum)
        throw "Invalid vertex s";
    if (t < 0 || t >= G.vexnum)
        throw "Invalid vertex t";

    using ArcNode = typename ALGraph<V, E, M>::ArcNode;

    // 在顶点 s 的邻接点链表中插入一个弧结点
    auto p = new ArcNode;
    p->weight = e;
    p->adjvex = t;

    p->nextarc = G.vexs[s].firstarc;
    G.vexs[s].firstarc = p;

    // 也可表示成  G.vexs[s].firstarc = new ArcNode { e, t, G.vexs[s].firstarc}

    G.arcnum++;
}

// 从一个顶点出发深度优先搜索 DFS(G,v,visit)
template <typename V, typename E, int M, typename F>
void DFS(ALGraph<V, E, M> &G, int v, F visit)
{
    // 访问顶点
    visit(G.vexs[v].data);
    G.visited[v] = true;

    // 依次从 v 的未访问的邻接点 w 出发深度优先遍历
    for (auto p = G.vexs[v].firstarc; p; p = p->nextarc)
    {
        int w = p->adjvex;
        if (!G.visited[w])
        {
            DFS(G, w, visit);
        }
    }
}

// 深度优先搜索 DFSTraverse(G,visit)
template <typename V, typename E, int M, typename F>
void DFSTraverse(ALGraph<V, E, M> &G, F visit)
{
    // 每个顶点的访问标志设成未访问
    for (int v = 0; v < G.vexnum; v++)
    {
        G.visited[v] = false;
    }

    // 从一个未访问的顶点出发深度优先搜索
    for (int v = 0; v < G.vexnum; v++)
    {
        if (!G.visited[v])
        {
            DFS(G, v, visit);
        }
    }
}

#include "sqqueue.h"

// 从顶点 v 出发广度优先搜索 BFS(G,v,visit)
template <typename V, typename E, int M, typename F>
void BFS(ALGraph<V, E, M> &G, int v, F visit)
{
    // 访问顶点 v
    visit(G.vexs[v].data);
    G.visited[v] = true;

    // 依次访问 v 的未访问的邻接点
    // 利用队列进行广度优先搜索
    SqQueue<int, M * M> Q;
    InitQueue(Q);
    EnQueue(Q, v);

    while (!QueueEmpty(Q))
    {
        // 取出访问过的顶点 v
        int v;
        DeQueue(Q, v);
        // 遍历 v 的邻接点，访问未访问的邻接点 w 并入队列
        for (auto p = G.vexs[v].firstarc; p; p = p->nextarc)
        {
            int w = p->adjvex;
            if (!G.visited[w])
            {
                visit(G.vexs[w].data);
                G.visited[w] = true;
                // 访问过的顶点入队列
                EnQueue(Q, w);
            }
        }
    }
}

// 广度优先搜索 BFSTraverse(G,visit)
template <typename V, typename E, int M, typename F>
void BFSTraverse(ALGraph<V, E, M> &G, F visit)
{
    // 每个顶点的访问标志设成未访问
    for (int v = 0; v < G.vexnum; v++)
    {
        G.visited[v] = false;
    }
    // 从一个未访问的顶点开始出发广度优先搜索
    for (int v = 0; v < G.vexnum; v++)
    {
        if (!G.visited[v])
        {
            BFS(G, v, visit);
        }
    }
}